package sort;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.concurrent.ThreadLocalRandom;

/**
 * 七大排序——实现
 */


public class SevenSort {
    private static ThreadLocalRandom random = ThreadLocalRandom.current();//产生一个随机数
    public static void main(String[] args) {
        int n = 1000000;
        int[] arr = SortHelper.genraRandomArray(n, 0, Integer.MAX_VALUE);
        int[] arr1 = SortHelper.arrCopy(arr);
        int[] arr2 = SortHelper.arrCopy(arr);
        int[] arr3 = SortHelper.arrCopy(arr);
        int[] arr4 = SortHelper.arrCopy(arr);
        int[] arr5 = SortHelper.arrCopy(arr);
        int[] arr6 = SortHelper.arrCopy(arr);
        int[] arr7 = SortHelper.arrCopy(arr);
        int[] arr8 = SortHelper.arrCopy(arr);
        int[] arr9 = SortHelper.arrCopy(arr);
        int[] arr10 = SortHelper.arrCopy(arr);
        int[] arr11 = SortHelper.arrCopy(arr);
        int[] arr12 = SortHelper.arrCopy(arr);
//        SortHelper.testSort(arr, "selectionSort");//选择排序——直接选择排序
//        SortHelper.testSort(arr1, "selectionSortOP");//双向选择排序
        SortHelper.testSort(arr2, "heapSort");//堆排序，原地排序
      //  SortHelper.testSort(arr3, "bubbleSort");// 冒泡排序
//        SortHelper.testSort(arr4, "insertionSort");// 直接插入排序
//        SortHelper.testSort(arr5, "insertionSortBS");// 二分插入排序（直接插的优化）
        SortHelper.testSort(arr6, "shellSort");// 希尔排序
        SortHelper.testSort(arr7, "mergeSort");// 归并排序
        SortHelper.testSort(arr8, "mergeSortNonRecursion");// 归并排序,非递归写法
        SortHelper.testSort(arr9, "quickSort");// 快速排序
      //  SortHelper.testSort(arr10, "quickSortNonRecursion");// 快速排序--迭代写法
        SortHelper.testSort(arr11, "quickSortHoare");// 快速排序--挖坑分区法



//        //int[] arr = {19,27,13,22,3,1,6,5,4,2,110,65,70,98,72};
//        int[] arr = {9,1,2,5,7,4,8,6,3,5};
//        //调用刚刚写的原地排序方法
//        mergeSortNonRecursion(arr);
//        System.out.println(Arrays.toString(arr));
//
    }

    /**
     * 选择排序——直接选择排序
     */
    public static void selectionSort(int[] arr){
        //最开始的无序区间 [i....n)
        //有效区间[]为空
        //最外层的for循环指的循环走的趟数，每走一趟外层循环，就有一个最小值放在了正确的位置
        for (int i = 0; i < arr.length - 1; i++) {
            //min指的是最小元素的下标
            int min = i;
            //内存循环在查找当前无序区间的最小值索引
            for (int j = i + 1 ; j < arr.length; j++) {
                if(arr[min] > arr[j]){ //找到了 j对应的元素比当前最小值还小
                    min = j;
                }
            }
            //min变量此刻一定保存了当前无序区间的最小值索引
            // 有序区间[0..i) + 1
            // 无序区间[i..n) - 1
            swap(arr,i,min);
        }

    }

    /**
     * 双向选择排序
     * @param arr
     */
    public static void selectionSortOP(int[] arr) {
        int low = 0;
        int high = arr.length - 1;
        // low == high => 无序区间只剩下最后一个元素，其实整个数组已经有序了。
        while (low < high) {
            int min = low;
            int max = low;
            for (int i = low + 1; i <= high; i++) {
                if (arr[i] < arr[min]) {
                    min = i;
                }
                if (arr[i] > arr[max]) {
                    max = i;
                }
            }
            // 此时min对应了最小值索引，交换到无序区间的最前面
            swap(arr,min,low);
            // 边界条件 low == max
            if (max == low) {
                //因为经过上面最小值的换，此刻的lou是最小值了，最大值在min索引处
                max = min;
            }
            swap(arr,max,high);
            low ++;
            high --;
        }
    }


    /**
     * 冒泡排序
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean isSwaped = false;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {

                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    //swap(arr,j,j + 1);
                    isSwaped = true;
                }
            }
            if (!isSwaped) {
                // 内层没有元素交换，此时整个数组已经有序
                break;
            }
        }
    }

    /**
     * 直接插入排序
     * 已排序区间[0..i)  => 默认第一个元素就是已经排好序的区间
     * 待排序区间[i...n)
     * @param arr
     */
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            // 已排序区间[0...1)
            // 待排序区间[i ..n)
            // 选择无序区间的第一个元素，不断向前看
            // 注意看内层循环的终止条件 j >= 1而不是 j >= 0 ?
            // 因为此时arr[j] 不断向前看一个元素  j - 1 要合法 j - 1 >= 0
            for (int j = i; j >= 1 && arr[j] < arr[j - 1]; j--) {
                swap(arr,j,j - 1);
                //把判断条件加到循环条件里面
//                // 边界
//                if (arr[j] > arr[j - 1]) {
//                    // arr[i] 恰好是有序区间的后一个元素，无序区间的第一个元素
//                    // 当前无序区间的第一个元素 > 有序区间最后一个元素
//                    break;
//                }else {
//                    swap(arr,j,j - 1);
//                }
            }
        }
    }


    /**
     * 二分插入排序
     * @param arr
     */
    public static void insertionSortBS(int[] arr) {
        // 有序区间[0..i)
        // 无序区间[i..n)
        for (int i = 0; i < arr.length; i++) {
            int val = arr[i];
            // 有序区间[left...right)
            int left = 0;
            int right = i;
            while (left < right) {
                int mid = (left + right) / 2;
                if (val < arr[mid]) {
                    right = mid;
                }else {
                    // val >= arr[mid]
                    left = mid + 1;
                }
            }
            // 搬移[left..i)的元素
            for (int j = i; j > left ; j--) {
                arr[j] = arr[j - 1];
            }
            // left就是待插入的位置
            arr[left] = val;
        }
    }

    /**
     * 希尔排序 - 缩小增量排序，按照 gap 将原数组分为gap子数组，子数组内容先排序，不断缩小gap值，直到 gap = 1
     * 当 gap = 1时，整个数组已经近乎有序，只需要最后再来一次插入排序即可
     * @param arr
     */
    public static void shellSort(int[] arr){
        int gap = arr.length >> 1;//因为位运算就最快的效率

        while(gap >= 1){
            //按照gap分组后，组内进行插入排序。
            insertionSortByGap(arr, gap);
            gap = gap >> 1;
        }

    }

    /**  希尔排序的辅助方法
     * 按照 gap进行分组，然后插入排序
     * 可以想象挤兑情况，假设此时 gap = 1 ，那就跟插入排序一模一样
     * @param arr
     * @param gap
     */
    private static void insertionSortByGap(int[] arr, int gap) {

        //i++ ： 新元素比有序数组最大值要小时，才需要进行插入排序操作~
        for (int i = gap; i < arr.length; i++) {                 //距离为gap的元素才算是一组内的
            for (int j = i; j - gap >= 0 && arr[j] < arr[j - gap] ; j -= gap) {
                    swap(arr, j, j - gap);
            }
        }
    }

    /**
     * 归并排序
     */
    public static void mergeSort(int[] arr){
        mergeSortInternal(arr, 0, arr.length - 1);
    }

    /**
     * 迭代实现归并排序(了解)
     */
    public static void mergeSortNonRecursion(int[] arr) {
        // 最外层循环表示每次合并的子数组的元素个数
        // 子数组为1个元素，第二次循环2个元素，第三次循环合并4个元素，第四次8个元素 ..
        // 直到整个数组合并完成
        for (int sz = 1;sz <= arr.length ;sz += sz) {
            // 内存循环变量i就是每次合并操作的开始索引l
            // [8,6,2,3,1,5,7,4]  => [2,3,6,8]  [1,4,5,7]
            //                                             i
            for (int i = 0; i + sz < arr.length; i += sz + sz) {
                // 边界i + sz + sz - 1 > arr.length
                merge(arr,i,i + sz - 1,Math.min(i + sz + sz - 1,arr.length - 1));
            }
        }
    }

    /**
     * 在arr[l....r] 上进行归并排序
     */
    private static void mergeSortInternal(int[] arr, int l, int r) {

//        if(l >= r){
//            return;
//        }
        if(r - l <= 15){
            insertionSort(arr,l,r);//15是实验得来数据，小于15的数组插入排序更快
            return;
        }


        int min = l + ((r - l) >> 1);//防止数据过大溢出，把多余部分除以 2就是一半的长度
        mergeSortInternal(arr,l, min);
        mergeSortInternal(arr,min + 1, r);
        //此时数组arr【l..min） 和 arr【min + 1 .... r）已经分别有序 只剩下合并两个数组

       // 就用合并链表的操作
      //  merge(arr, l, min, r);
      // 1.到底什么时候才需要合并 arr[mid] < arr[mid + 1] 说明？arr[mid] 数组1的最大值 arr[mid + 1]数组2的最小值
      // 整个数组已经有序了，那你还合并个der
        if(arr[min] > arr[min + 1]){
            merge(arr, l, min, r);
        }

    }

    /**
     * 在arr[l..r]上进行插入排序
     */
    private static void insertionSort(int[] arr, int l, int r) {
        for (int i = l + 1; i <= r; i++) {
            for (int j = i ; j >= l + 1 && arr[j] < arr[j - 1] ; j--) {
                    swap(arr,j, j - 1);
            }
        }
    }

    /**
     * 将有序子数组arr[l..mid] 和 有序arr[mid + 1...r] 合并为一个大的有序数组arr[l..r]
     * 将两个有序的子数组合并成一个大的有效数组
     */
    private static void merge(int[] arr, int l, int min, int r) {
        int[] aux = new int[r - l + 1];//创建一个l。。r范围等长的数组
        // l = 2; r = 4
        //arr[2, 3, 4]
        //aux[0, 1, 2] 在aux中下标差了 l 的偏移量
        for (int i = 0; i < aux.length; i++) {
            aux[i] = arr[i + l];
            // aux的索引下标0...arr.length - 1
            // arr的下标l...r
        }//循环完后把arr中 l到r范围的元素复制完毕   //注释：之所以要复制，是因为不复制而进行合并的话，
                                            //可能在过程中会覆盖掉还没进行比较的元素
        //第一个数组的下标，左数组
        int i = l;                 //这两个变量是记录左右数组走到哪了
        //第二个数组的下标，右数组
        int j = min + 1;
        for (int k = l; k <= r; k++) {
            if(i > min){
                //第一个数组已经遍历完毕
                arr[k] = aux[j - l];
                j ++;
            }else if(j > r){
                //第二个数组已经遍历完毕
                arr[k] = aux[i - l];
                i ++;
            }else if(aux[i - l] < aux[j - l]){ //这里要 减去 偏移量 l才是aux数组的索引
                //左数组此刻元素 小于 右数组此刻元素
                arr[k] = aux[i - l];
                i ++;
            }else{
                //左数组此刻元素 大于 右数组此刻元素
                arr[k] = aux[j - l];
                j ++;
            }

        }

    }

    /**
     *  快速排序--基于算法导论的分区思想
     */
    public static void quickSort(int[] arr){
        quickSortInternal(arr, 0, arr.length - 1);
    }

    /**
     *  递归实现快速排序
     */
    private static void quickSortInternal(int[] arr, int l, int r) {
        //终止条件：当元素为空，或者只剩下一个元素的时候就停止循环
//        if(l >= r){
//            return;
//        }
        //优化2：当数组元素小于 15 时，直接使用插入排序会更加的快
        if(r - l <= 15){
            insertionSort(arr, l, r);
            return;
        }

        int p = partition(arr, l, r);

        quickSortInternal(arr, l, p - 1);
        quickSortInternal(arr, p + 1, r);

    }

    /**
     * 快速排序的辅助工具： 对整个数组进行分区，小于 v在左，大在右，并返回中间索引
     *  基于算法导论的分区思想
     */
    private static int partition(int[] arr, int l, int r) {
        // 1.优化1.使用一个随机位置作为分区点，避免快排在近乎有序数组上的性能退化
        //选择需要随机选择一个元素到第一个位置上来
        int randomIndex = random.nextInt(l, r);
        swap(arr, l, randomIndex);//把第一个位置上的元素随机跟个元素交换位置
        //选择默认值
        int v = arr[l];
        //因为小于v的索引是 l + 1到 j
        //最开始小于v数组应该为空 [ ]
        int j = l;
        for (int i = l + 1; i <= r ; i++) {
            if(arr[i] < v){
                swap(arr, j + 1, i);
                j ++;//扩大小于v的范围
            }
        }
        //最后再交换 l 和 j元素的位置就完成分区了
        swap(arr, l, j);
        return j;
    }

    /**
     * 快速排序的迭代写法
     * @param arr
     */
    public static void quickSortNonRecursion(int[] arr) {
        Deque<Integer> stack = new ArrayDeque<>();
        // r
        stack.push(arr.length - 1);
        // l
        stack.push(0);
        // 每次从栈中取出两个元素，这辆个元素就是待排序区间的l..r
        while (!stack.isEmpty()) {
            int l = stack.pop();
            int r = stack.pop();
            if (l >= r) {
                // 当前子数组已经处理完毕
                continue;
            }
            int p = partition(arr,l,r);
            // 继续入栈两个子区间
            stack.push(p - 1);
            stack.push(l);

            stack.push(r);
            stack.push(p + 1);
        }
    }

    /**
     *  快速排序，使用挖坑分区法
     * @param arr
     */
    public static void quickSortHoare(int[] arr){
        //其他步骤都跟正常的快排没区别，就是在分区有差别
        quickSortInternalHoare(arr, 0, arr.length - 1);
    }

    /**
     * 挖坑法--快排递归
     */
    private static void quickSortInternalHoare(int[] arr, int l, int r) {
        if(r - l <= 15){
            insertionSort(arr, l, r);
            return;
        }
        int p = partitionHoare(arr, l, r);
        quickSortInternalHoare(arr, l, p - 1);
        quickSortInternalHoare(arr, p + 1, r);

    }

    /**
     * 挖坑法实现快排分区
     */
    private static int partitionHoare(int[] arr, int l, int r) {
        int randomIndex = random.nextInt(l, r);//随机数
        swap(arr, l, randomIndex);

        int v = arr[l];
        int i = l;
        int j = r;

        while(i < j){
            // 先让j从后向前扫描到第一个 < v的元素停止
            while(i < j && arr[j] >= v){
                j --;
            }
            arr[i] = arr[j];

            // 再让i从前向后扫描到第一个 > v的元素停止
            while(i < j && arr[i] <= v){
                i ++;
            }
            arr[j] =  arr[i];

        }//分区完后 i == j
        arr[i] = v;
        return i;
    }


    //原地排序
    public static void heapSort(int[] arr){
        //1.先将任意数组进行heapify调整为最大堆
        for(int i = (arr.length - 1 - 1) / 2 ; i >= 0; i--){
            //不断进行着 siftDown 操作
            siftDown(arr, i, arr.length);
        }
        //2 不断交换堆顶元素到数组末尾，每交换一个元素，就有一个元落在了最终位置
        for (int i = arr.length - 1; i > 0 ; i--) {
            // arr[i] 就是未排序数组的最大值，交换末尾
            swap(arr,0, i);
            siftDown(arr,0, i);//这里数组长度必须传 i 因为每成功一次相当于
            //末尾位置确定了，就不需要被下层操作的影响。逻辑上相当于数组没有了这个元素位置。
        }

    } //注释：arr. length - 1是最后一个元素的索引
     //而 (arr.length - 1 - 1) / 2 是找最后一个元素的父类索引

    /**
     * 交换两个元素的位置
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     *
     * @param arr
     * @param i  //当前哪个位置的元素需要跟树顶换位置，进行下层操作
     * @param length //左子树大于总长度就不用下层了
     */
    private static void siftDown(int[] arr, int i, int length) {
        //终止条件，不存在左子树索引就结束
        while(2 * i + 1 < length){
            int j = 2 * i + 1;
            if(j + 1 < length && arr[j + 1] > arr[j] ){
                j = j + 1;
            }
            //此时 j索引就是左右子树中最大值的索引
            if(arr[i] > arr[j]){
                break;
            }else{
                swap(arr, i,j);
                i = j;
            }

        }
    }
}
